/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/inorder-successor-in-bst
   @Language: C++
   @Datetime: 19-03-29 14:11
   */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


class Solution {
public:
	/*
	 * @param root: The root of the BST.
	 * @param p: You need find the successor node of p.
	 * @return: Successor of p.
	 */
	TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
		// write your code here
		TreeNode *node=NULL;
		for(; root && p; ){
			if (root->val>p->val){
				node=root;
				root=root->left;
			}
			else root=root->right;
		}
		return node;
	}
};
